package algorithm.middle;

import jdk.nashorn.internal.runtime.regexp.joni.Regex;

import java.io.Console;
import java.util.ArrayList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: NumDecodings91
 * @description: 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
 * <p>
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
 * <p>
 * "AAJF" ，将消息分组为 (1 1 10 6)
 * "KJF" ，将消息分组为 (11 10 6)
 * 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
 * <p>
 * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
 * <p>
 * 题目数据保证答案肯定是一个 32 位 的整数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "12"
 * 输出：2
 * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
 * 示例 2：
 * <p>
 * 输入：s = "226"
 * 输出：3
 * 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/decode-ways
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/4/219:00
 * @since V1.0
 */
public class NumDecodings91 {
    static final int MAX = 26;

    public static void main(String[] args) {
        System.out.println(numDecodings("230"));

//        String value = "500楼";
//        System.out.println(value.matches("^([1-9]\\d*[楼])"));

//        String str = null+"";
//        System.out.println(str);
//        System.out.println(str.length());
    }

    //动态规划
    //dp[i] = dp[i-1] + dp[i-2](如果s[i]和s[i-1]能组合则加这个1) 否则dp[i] = dp[i-1]
    //预处理 把s中的0都拼到前一个字符后面
    public static int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        //预处理
        ArrayList<Integer> arr = new ArrayList<>();
        int i = 0;
        while (i + 1 < s.length()) {
            if (s.charAt(i + 1) != '0') {
                if (s.charAt(i) - '0' == 0) return 0;
                arr.add(s.charAt(i) - '0');
            } else {
                if ((s.charAt(i) - '0') * 10 > MAX) return 0;
                arr.add((s.charAt(i) - '0') * 10);
                i++;
            }
            i++;
        }
        if (i<s.length()){
            if (s.charAt(i) == '0')  return 0;
            arr.add(s.charAt(i) - '0');
        }
        System.out.println(arr);
        int[] dp = new int[arr.size() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int j = 2; j <arr.size()+1; j++) {
            int index = j-1;
            if (Integer.parseInt(""+arr.get(index - 1)+arr.get(index)) <= MAX) {
                dp[j] = dp[j - 1] + dp[j - 2];
            }else {
                dp[j] = dp[j - 1];
            }
        }
        return dp[arr.size()];
    }

    public int 官方题解(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }

}
